import java.util.Scanner;
public class Leetcode {
}


//牛客:【模板】完全背包
// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt() , V = in.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        int[][] dp1 = new int[n+1][V+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= V; j++){
                dp1[i][j] = dp1[i-1][j];
                if(j >= v[i])
                    dp1[i][j] = Math.max(dp1[i][j] , dp1[i][j-v[i]]+w[i]);
            }
        }

        System.out.println(dp1[n][V]);

        int[][] dp2 = new int[n+1][V+1];
        for(int j = 1; j<= V; j++) dp2[0][j] = -1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= V; j++){
                dp2[i][j] = dp2[i-1][j];
                if( j >= v[i] && dp2[i][j-v[i]] != -1)
                    dp2[i][j] = Math.max(dp2[i][j] , dp2[i][j-v[i]]+w[i]);
            }
        }

        System.out.println(dp2[n][V] == -1 ? 0 : dp2[n][V]);
    }
}

//滚动数组优化
class Main2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt() , V = in.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        int[] dp1 = new int[V+1];
        for(int i = 1; i <= n; i++){
            for(int j = v[i]; j <= V; j++){
                dp1[j] = Math.max(dp1[j] , dp1[j-v[i]]+w[i]);
            }
        }

        System.out.println(dp1[V]);

        int[] dp2 = new int[V+1];
        for(int j = 1; j<= V; j++) dp2[j] = -1;
        for(int i = 0; i <= n; i++){
            for(int j = v[i]; j <= V; j++){
                if(dp2[j-v[i]] != -1)
                    dp2[j] = Math.max(dp2[j] , dp2[j-v[i]]+w[i]);
            }
        }

        System.out.println(dp2[V] == -1 ? 0 : dp2[V]);
    }
}